/**
 * 671. 二叉树中第二小的节点
 * https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/
 */
public class Solutions_671 {
    public static void main(String[] args) {
//        TreeNode root = new TreeNode(2);
//        root.left = new TreeNode(2);
//        root.right = new TreeNode(2);  // output: -1

        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);  // output: 5

        int result = findSecondMinimumValue(root);
        System.out.println(result);
    }
    /**
     * 题义分析：
     * 特殊二叉树，特殊性所在：
     * 1. 并且每个节点的子节点数量只能为 2 或 0（要么没有子节点，要么有两个子节点）
     * 2. 如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
     * （所以原始根节点值只能是左右子节点中的较小值，不存在根节点值小于其左右子节点值的情况）
     *  你需要输出所有节点中的第二小的值。（即找到大于根节点的值）
     * 解题思路：逆推
     * root 中的每个节点的值等于两个子节点（如果有子节点的话）中较小的一个
     * 那么需要求 root 中第二小的值时，就是转换为求大于 root 的元素
     *    2
     *   / \
     *  2   5
     *     / \
     *    5   7
     * 比如 5，大于根节点 2，那么就不用再往下递归了，因为节点 5 的子树下的元素，一定都大于等于 5
     *      2
     *    /  \
     *   2    5
     *  / \  / \
     * 2  4  5  7
     * 比如子节点为 2，4 的父节点 2，其节点值等于其父节点值 2，那么子树中还是有可能存在大于 2 的元素，比如 4
     * 因为子节点为 2，4 的父节点 2 的取值，是其左右了节点中的最小值
     * 那么要求大于 2 的元素时，就需要取子节点中的较大值，返回结果
     */
    public static int findSecondMinimumValue(TreeNode root) {
        if (root == null || root.left == null) {
            return -1;
        }
        int left = root.left.val;
        int right = root.right.val;
        if (left == root.val) {
            // 返回的是 -1 时，说明左子树下，没有大于 root.val 的元素
            left = findSecondMinimumValue(root.left);
        }
        if (right == root.val) {
            // 返回的是 -1 时，说明右子树下，没有大于 root.val 的元素
            right = findSecondMinimumValue(root.right);
        }
        if (left != -1 && right != -1) {
            // 左右子节点都不等于根节点 root.val，那么第二小的值就是左右了节点值较小的一个
            return Math.min(left, right);
        }
        // 两种情况：
        // 1. 左右子树中全部的节点值都等于根节点值时，那么不存在第二小的值，返回 -1
        // 2. 左子树或右子树中，有一侧存在大于根节点值的节点，那么第二小的值就是不等于 -1 的一侧
        return left == -1 ? right : left;
    }
}
